#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef struct
{	int col[MaxSize];				
	int top;						
} StackType;						
void dispasolution(StackType St)   		
{	static int count=0;				
	printf("  第%d个解:",++count);
	for (int i=1;i<=St.top;i++)
		printf("(%d,%d) ",i,St.col[i]);
	printf("\n");
}
bool place(StackType St,int k,int j)
{	int i=1;
	if (k==1) return true;				
	while (i<=k-1)					
	{	if ((St.col[i]==j) || (abs(j-St.col[i])==abs(i-k)))
			return false;			
		i++;
	}
	return true;						
}
void queen(int n)					
{
	int k;
	bool find;
	StackType St;						
	St.top=0;						
	St.top++; St.col[St.top]=0;			
	while (St.top!=0)				
	{	k=St.top;					
		find=false;						
		for (int j=St.col[k]+1;j<=n;j++)
			if (place(St,k,j))			
			{	St.col[St.top]=j;	
				find=true;				
				break;				
			}
		if (find)					
		{	if (k==n)				
				dispasolution(St);
			else						
			{	St.top++;
				St.col[St.top]=0;	
			}
		}
		else						
			St.top--;				
	}
}
int main()
{	int n;							
	printf("皇后问题(n<20) n=");
	scanf("%d",&n);
	if (n>20)
		printf("n值太大\n");
	else
	{	printf(" %d皇后问题求解如下：\n",n);
		queen(n);
	}
	return 1;
}
